package com.company.剑指offer每日刷题.普通版;

import java.util.Arrays;

/**
 * 剑指 Offer 57. 和为s的两个数字
 * 输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
 * 示例 1：
 *
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[2,7] 或者 [7,2]
 * 示例 2：
 *
 * 输入：nums = [10,26,30,31,47,60], target = 40
 * 输出：[10,30] 或者 [30,10]
 * 限制：
 *
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^6
 * */
public class TwoSum {

    /**
     * 方法1： 二分法
     * 思路： 数组是递增的，可以考虑用到二分查找。
     *       先固定一个数字，然后另一个数字用二分法查找。
     * 时间复杂度： O(nlogn)
     * */
    public int[] twoSum(int[] nums, int target) {
        int i = 0;
        int[] res = new int[2];
        while((nums[i]<<1) <= target && i < nums.length){
            int left=i,right = nums.length -1;
            res[0] = nums[i];
            while(left <= right){
                int mid = left + (right - left)/2;
                if(nums[mid] == target - res[0]){
                    res[1] = nums[mid];
                    return res;
                }else if(nums[mid] > target - res[0]){
                    right = mid -1;
                }else{
                    left = mid +1;
                }
            }
            i++;
        }
        return new int[0];
    }

    public static void main(String[] args) {
        TwoSum obj =new TwoSum();
        int[] ints = obj.twoSum(new int[]{10, 26, 30, 31, 47, 60}, 40);
        System.out.println(Arrays.toString(ints));
    }
}
